//递增子序列
class Solution {
public:
    vector<vector<int>>res;
    vector<int>tmp;
    vector<vector<int>> findSubsequences(vector<int>& nums) 
    {
        dfs(nums,0);
        return res;
    }
    void dfs(vector<int>& nums,int curi)
    {
        if(tmp.size()>=2)
        {
            res.push_back(tmp);
        }
        unordered_set<int>s;//定义在栈上的哈希表 每调用一处dfs都有一个新的
        for(int i=curi;i<nums.size();i++)
        {
            if(!tmp.empty() && nums[i]<tmp.back() || s.find(nums[i])!=s.end()) continue;
                s.insert(nums[i]);
                tmp.push_back(nums[i]);
                dfs(nums,i+1);
                tmp.pop_back();
        }
    }
};
// 复原IP地址

class Solution {
public:
    vector<string>res;
    vector<string>tmp;
    string str;
    //判断截取位置是否合法
    //左闭右闭区间
    bool isright(string& s,int left,int right)
    {
        if(left>right) return false;

        //0开头的数字不合法
        if(s[left]=='0' && left<right) return false;

        //判断数字是否在【0，255】
        // int num=0;
        // for(int i=left;i<=right;i++)
        // {
        //     if(s[i]<'0' || s[i]>'9') return false;
        //     num=num*10+(s[i]-'0');
        //     if(num>255) return false;
        // }
        string s1=s.substr(left,right-left+1);
        int num=atoi(s1.c_str());
        if(num>255 || num<0) return false;

        return true;
    }
    void dfs(string&s,int curi,int size)
    {
        if(size==3)
        {
            //已经拿了三段了 判断一下最后一段是否合法
            if(isright(s,curi,s.size()-1))
            {
                str=s.substr(curi);
                tmp.push_back(str);
                string ans=tmp[0]+'.'+tmp[1]+'.'+tmp[2]+'.'+tmp[3];
                tmp.pop_back();
                res.push_back(ans);
            }
            return;
        }
        for(int i=curi;i<s.size();i++)
        {
            if(isright(s,curi,i))
            {
                str=s.substr(curi,i-curi+1);
                tmp.push_back(str);
                dfs(s,i+1,size+1);
                tmp.pop_back();
            }
            else
            {
                break;
            }
        }

    }
    vector<string> restoreIpAddresses(string s) 
    {
        res.clear();
        tmp.clear();
        if (s.size() < 4 || s.size() > 12) return res;
        dfs(s,0,0);
        return res;
    }
};
//分割回文串
class Solution {
public:
    //分割问题和组合问题是类似的
    vector<vector<string>> res;
    vector<string>tmp;
    bool isright(string& s,int left,int right)
    {
        while(left<right)
        {
            if(s[left]==s[right])
            {
                left++;
                right--;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> partition(string s) 
    {
        if(s.empty()) return res;
        dfs(s,0);
        return res;
    }
    void dfs(string& s,int curx)
    {
        if(curx==s.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=curx;i<s.size();i++)
        {
            if(isright(s,curx,i))
            {
                string str=s.substr(curx,i-curx+1);
                tmp.push_back(str);
                dfs(s,i+1);
                tmp.pop_back();
            }
            else
            {
                continue;
            }
        }
    }
};